#include "myGraph.h"
#include <iostream>
#include <queue>
#include <sstream>
#include <string>

using namespace std;

EdgeNode::EdgeNode() : dest(0), link(nullptr) {}

EdgeNode::EdgeNode(int dest, EdgeNode *link) : dest(dest), link(link) {}

EdgeNode::~EdgeNode()
{
    if (link)
    {
        delete link;
    }
}

int EdgeNode::getDest()
{
    return dest;
}

EdgeNode *EdgeNode::getNext()
{
    return link;
}

void EdgeNode::setDest(int dest)
{
    this->dest = dest;
}

void EdgeNode::setNext(EdgeNode *link)
{
    this->link = link;
}

VertexNode::VertexNode() : data('\0'), firstEdge(nullptr) {}

VertexNode::VertexNode(char data, EdgeNode *firstEdge) : data(data), firstEdge(firstEdge) {}

VertexNode::~VertexNode()
{
    if (firstEdge)
    {
        EdgeNode *temp = firstEdge;
        while (temp)
        {
            EdgeNode *todelete = temp;
            temp = temp->getNext();
            delete todelete;
        }
    }
}

char VertexNode::getData()
{
    return data;
}

EdgeNode *VertexNode::getFirstEdge()
{
    return firstEdge;
}

void VertexNode::setData(char data)
{
    this->data = data;
}

void VertexNode::setFirstEdge(EdgeNode *firstEdge)
{
    this->firstEdge = firstEdge;
}

MyGraph::MyGraph() : nodeNum(0), edgeNum(0), VexList(nullptr) {}

MyGraph::MyGraph(int nodeNum, int edgeNum, char *nodeList, int *edgeStartList, int *edgeEndList)
{
    this->nodeNum = nodeNum;
    this->edgeNum = edgeNum;
    VexList = new VertexNode[nodeNum];
    for (int i = 0; i < nodeNum; i++)
    {
        VexList[i].setData(nodeList[i]);
        VexList[i].setFirstEdge(nullptr);
    }
    for (int i = 0; i < edgeNum; i++)
    {
        int start = edgeStartList[i];
        int end = edgeEndList[i];
        EdgeNode *newnode = new EdgeNode(end, VexList[start].getFirstEdge());
        VexList[start].setFirstEdge(newnode);
        // 无向图，添加反向边
        newnode = new EdgeNode(start, VexList[end].getFirstEdge());
        VexList[end].setFirstEdge(newnode);
    }
}

MyGraph::~MyGraph()
{
    delete[] VexList;
}

int MyGraph::getNodeNum()
{
    return nodeNum;
}

int MyGraph::getEdgeNum()
{
    return edgeNum;
}

string MyGraph::printGraph()
{
    string result;
    for (int i = 0; i < nodeNum; i++)
    {
        result = result + VexList[i].getData() + ": ";
        EdgeNode *current = VexList[i].getFirstEdge();
        while (current)
        {
            result = result + VexList[current->getDest()].getData() + " ";
            current = current->getNext();
        }
        result.pop_back(); // 移除最后一个空格
        if (i != nodeNum - 1)
        {
            result += "\n";
        }
    }
    return result;
}

void MyGraph::DFS(int v, int *visited, string &result)
{
    visited[v] = 1;
    result = result + VexList[v].getData() + " ";
    EdgeNode *current = VexList[v].getFirstEdge();
    while (current)
    {
        int next = current->getDest();
        if (!visited[next])
        {
            DFS(next, visited, result);
        }
        current = current->getNext();
    }
}

string MyGraph::graph_DFS_Traverse()
{
    string result;
    int *visited = new int[nodeNum];
    for (int i = 0; i < nodeNum; i++)
    {
        visited[i] = 0;
    }
    for (int i = 0; i < nodeNum; i++)
    {
        if (!visited[i])
        {
            DFS(i, visited, result);
        }
    }
    delete[] visited;
    return result;
}

void MyGraph::BFS(int v, int *visited, string &result)
{
    visited[v] = 1;
    queue<int> q;
    q.push(v);
    while (!q.empty())
    {
        int current = q.front();
        q.pop();
        result = result + VexList[current].getData() + " ";
        EdgeNode *edge = VexList[current].getFirstEdge();
        while (edge)
        {
            int next = edge->getDest();
            if (!visited[next])
            {
                visited[next] = 1;
                q.push(next);
            }
            edge = edge->getNext();
        }
    }
}

string MyGraph::graph_BFS_Traverse()
{
    string result;
    int *visited = new int[nodeNum];
    for (int i = 0; i < nodeNum; i++)
    {
        visited[i] = 0;
    }
    for (int i = 0; i < nodeNum; i++)
    {
        if (!visited[i])
        {
            BFS(i, visited, result);
        }
    }
    delete[] visited;
    return result;
}